package demo1;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-08-04
 * Time: 8:58
 */
// 直接插入排序
public class InsertSort {

    /**
     * 时间复杂度 : 每一次比较往前比较 N 个元素, 每个元素都要往前比较. 最坏情况下位降序排列, 时间复杂度为 O(N^2)
     * 空间复杂度 : 没有开辟新的额外空间, 只操作原来数组 O(1)
     * 稳定性 : 两个元素相等的时候, 不进行交换, 还在原地, 因此是稳定的
     */
    public void insertSort(int[] array) {

        // 从第二个元素开始比较
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i]; // 记录每一次开始比较的元素\
            int j = i - 1;
            // tmp 和前面的每一个元素比较
            for (; j >= 0; j--) {
                // 升序排列
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    // 将这个元素放回原地址
                    // array[j + 1] = tmp;
                    break;
                }
            }

            // 如果此时比较的这个元素最小 tmp, 那么 j 会走至 -1 下标处, 此时 0 位置还是上一次的最小值, 并非此时的 tmp, 需要更新
            array[j + 1] = tmp;
        }

    }

    public static void main(String[] args) {
        int[] array = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        InsertSort insertSort = new InsertSort();
        insertSort.insertSort(array);
        System.out.println(Arrays.toString(array));
    }
}
